Formální síťová analýza¶
autor: Vojtěch Kaše (kase@ff.zcu.cz)
Úvod a cíle kapitoly¶
V tomto notebooku si budeme prakticky osvojovat koncepty síťové analýzy. Z veřejně dostupných dat si vytvoříme několik síťových grafů, které budeme dále upravovat, analyzovat a vizualizovat.
Jedním z nejhodnotnějších typů historických dat jsou sbírky dopisů, které nám umožňují sledovat kdo, s kým a kdy udřžoval kontakty. Řada těchto dopisních sbírek byla v posledních dekádách digitalizována. Existují tak například digitalizované kolekce sbírkek dopisů středověkých žen (https://epistolae.ctl.columbia.edu/letters/) nebo rozsáhlá kolekce raně novověkých dopisů EMLO (=Early Modern Letters Online, http://emlo-portal.bodleian.ox.ac.uk). Některé tyto datasety umožňují přístup pouze pomocí prohlížeče, a tudíž se nehodí pro datově analytickou práci. Jiné jsou naopak vzorovými příklady datového kurátorství. Ty zde budeme používat.
Konkrétně využijeme dataset dopisů mezi britskými vědci konce 18. a celého 19. století Ɛpsilon (web), vyvíjený týmem z Cambridge University Digital Library.
Ɛpsilon opens up new research opportunities in the history of 19th century science by bringing correspondence data and transcriptions from multiple sources into a single cross-searchable digital platform. It currently holds details of over 50,000 letters and is growing.
Alespoň z pohledu datové analýzy je velkou devízou tohoto projektu fakt, že veškerá data jsou dostupná nejen pro potřeby prohledávání a pročítání na webu projektu, ale také ve velice úhledné a praktické formě dostupná na GitHubu (zde). Nachází se zde jak digitální edice každého jednotlivého dopisu podle standardu TEI-XML, tak i tabulky metadat ve formátu CSV. S těmi budeme níže pracovat my, když se je přímo z GitHubu načteme do našeho výpočetního prostředí.
Nejprve budeme pracovat s kolekcí dopisů Londínské Linneovské společnosti, která byla založena roku 1788 a existuje dodnes (wikipedia). Ač nese jméno významného švédského vědce Carla Linného (wikipedia), otce vědecké taxonomie, tato vědecká společnost vznikla v Anglii až po jeho smrti.
Tabulková data budeme zpracovávat pomocí knihovny pandas. K síťové analýze využijeme knihovnu networkX, jejíž dokumentaci doporučuji k projití si - zde).
Cvičení 1: Korespondence Linnevské společnosti¶
Extrakce a přehled dat¶
import numpy as np
import pandas as pd
import requests
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import regex
# navštívíme url adresu, kde jsou umístěny všechny csv soubory
# načteme HTTP odpověď do JSON formátu (není možné vždy, ale zde to funguje
resp_json = requests.get("https://github.com/cambridge-collection/epsilon-data/tree/main/csv").json()
Nyní si vypíšeme obsah načtených dat a zorientujeme v příslušné struktuře:
resp_json
Vidíme, že ve struktuře je možné nalézt výpis jednotlivých csv souborů, které nás zajímají - nacházejí se pod tagem "tree", ten je však zanořen v dalších tagách.
resp_json["payload"]["tree"]["items"]
[{'name': 'ampere.csv', 'path': 'csv/ampere.csv', 'contentType': 'file'},
{'name': 'darwin-correspondence.csv',
'path': 'csv/darwin-correspondence.csv',
'contentType': 'file'},
{'name': 'darwin-family-letters.csv',
'path': 'csv/darwin-family-letters.csv',
'contentType': 'file'},
{'name': 'faraday.csv', 'path': 'csv/faraday.csv', 'contentType': 'file'},
{'name': 'henslow.csv', 'path': 'csv/henslow.csv', 'contentType': 'file'},
{'name': 'herschel.csv', 'path': 'csv/herschel.csv', 'contentType': 'file'},
{'name': 'kemp.csv', 'path': 'csv/kemp.csv', 'contentType': 'file'},
{'name': 'linnean-society.csv',
'path': 'csv/linnean-society.csv',
'contentType': 'file'},
{'name': 'royal-society.csv',
'path': 'csv/royal-society.csv',
'contentType': 'file'},
{'name': 'somerville.csv',
'path': 'csv/somerville.csv',
'contentType': 'file'},
{'name': 'tyndall.csv', 'path': 'csv/tyndall.csv', 'contentType': 'file'}]
filenames = [item["name"] for item in resp_json["payload"]["tree"]["items"]]
filenames
['ampere.csv', 'darwin-correspondence.csv', 'darwin-family-letters.csv', 'faraday.csv', 'henslow.csv', 'herschel.csv', 'kemp.csv', 'linnean-society.csv', 'royal-society.csv', 'somerville.csv', 'tyndall.csv']
linnean = pd.read_csv("https://raw.githubusercontent.com/cambridge-collection/epsilon-data/main/csv/linnean-society.csv")
linnean.head()
| id | sender_surname | sender_forename | recipient_surname | recipient_forename | sorting_date | date | sender_address | recipient_address | source | languages | extent | filename | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | LINNEAN1 | Abbot | Charles | Smith | Sir James Edward | 1807-11-02 | 2 Nov 1807 | Bedford, Bedfordshire | NaN | GB-110/JES/ADD/1, The Linnean Society of London | eng | NaN | LINNEAN1.xml |
| 1 | LINNEAN2 | Butt | John Martin | Smith | Sir James Edward | 1798-09-17 | 17 Sep 1798 | Witley, Worcestershire | NaN | GB-110/JES/ADD/10, The Linnean Society of London | eng | NaN | LINNEAN2.xml |
| 2 | LINNEAN3 | Strutt | Jacob George | Smith | Sir James Edward | 1826-05-31 | 31 May 1826 | London | NaN | GB-110/JES/ADD/100, The Linnean Society of London | eng | NaN | LINNEAN3.xml |
| 3 | LINNEAN4 | Swainson | William | Smith | Sir James Edward | 1815-04-22 | 22 Apr 1815 | Palermo, Sicily | London | GB-110/JES/ADD/101, The Linnean Society of London | eng | NaN | LINNEAN4.xml |
| 4 | LINNEAN5 | Teesdale | Robert | Smith | Sir James Edward | 1789-11-18 | 18 Nov 1789 | London | London | GB-110/JES/ADD/102, The Linnean Society of London | eng | NaN | LINNEAN5.xml |
Vidíme zde výpis prvních pěti řádek datové tabulky. Ale kolik vlastně tabulka čítá položek a kolik že je sloupců? To zjistíme z atributu shape (atributem je vlastnost datového objektu - jednou z vlastností datového objektu podle standardu pd.DataFrame je jeho tvar, tj. počet řádků a sloupců.
linnean.shape
(3538, 13)
Než se pustíme do síťových analýz, ještě si upravíme hodnoty v některých sloupcích tak, aby se nám s nimi dobře pracovalo. Sloupec "sorting_date" vyjadřuje dataci daného dopisu ve velice úhledném a srozumitelném formátu (yyyy-mm-dd). Jelikož jsme však naše data načetl z prostého csv souboru, Python neví nic o tom, že za touto řadou čísel a pomlček se jedná o dataci; k tomu jej musíme nainstruovat.
V buňce níže za tímto účelem vytváříme nový sloupec s výmluvným názvem "datetime". Hodnoty v tomto sloupci jsou výsledkem použití (aplikování) funkce to_datetime() z knihovny pandas (pd) na hodnoty ve sloupci "sorting_date". Tato funkce "přeloží" jednotlivá čísla na roky, měsíce a dny.
linnean["datetime"] = linnean["sorting_date"].apply(pd.to_datetime)
linnean.head(5)
| id | sender_surname | sender_forename | recipient_surname | recipient_forename | sorting_date | date | sender_address | recipient_address | source | languages | extent | filename | datetime | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | LINNEAN1 | Abbot | Charles | Smith | Sir James Edward | 1807-11-02 | 2 Nov 1807 | Bedford, Bedfordshire | NaN | GB-110/JES/ADD/1, The Linnean Society of London | eng | NaN | LINNEAN1.xml | 1807-11-02 |
| 1 | LINNEAN2 | Butt | John Martin | Smith | Sir James Edward | 1798-09-17 | 17 Sep 1798 | Witley, Worcestershire | NaN | GB-110/JES/ADD/10, The Linnean Society of London | eng | NaN | LINNEAN2.xml | 1798-09-17 |
| 2 | LINNEAN3 | Strutt | Jacob George | Smith | Sir James Edward | 1826-05-31 | 31 May 1826 | London | NaN | GB-110/JES/ADD/100, The Linnean Society of London | eng | NaN | LINNEAN3.xml | 1826-05-31 |
| 3 | LINNEAN4 | Swainson | William | Smith | Sir James Edward | 1815-04-22 | 22 Apr 1815 | Palermo, Sicily | London | GB-110/JES/ADD/101, The Linnean Society of London | eng | NaN | LINNEAN4.xml | 1815-04-22 |
| 4 | LINNEAN5 | Teesdale | Robert | Smith | Sir James Edward | 1789-11-18 | 18 Nov 1789 | London | London | GB-110/JES/ADD/102, The Linnean Society of London | eng | NaN | LINNEAN5.xml | 1789-11-18 |
Ač hodnoty ve sloupci "datetime" vypadají stejně jako hodnoty ve sloupci "sorting_date", chovají se odlišně. Umožňují nám přímo studovat časovou distribuci našich dat. Výhody tohoto formátu si všimneme, když na daný sloupec aplikujeme vizualizační metodu hist():
linnean["datetime"].hist()
<Axes: >
linnean["18thcent?"] = linnean["datetime"] < pd.to_datetime("1801-01-01")
linnean["sender_agr"] = linnean.apply(lambda row: str(row["sender_surname"]).replace(" ", "_") + "_" + str(row["sender_forename"]).replace(" ", "_"), axis=1)
linnean["recipient_agr"] = linnean.apply(lambda row: str(row["recipient_surname"]).replace(" ", "_") + "_" + str(row["recipient_forename"]).replace(" ", "_"), axis=1)
Nyní se podíváme na osoby, který poslaly a přijaly největší množství dopisů:
linnean["sender_agr"].value_counts()
sender_agr
Smith_Sir_James_Edward 481
Goodenough_Samuel 222
Woodward_Thomas_Jenkinson 101
Roscoe_William 98
Johnes_Thomas 84
...
Erskine_David_Steuart 1
Upcher_Abbot 1
Walcott_William 1
Baker_William_Lloyd 1
Cullen_Charles_Sinclair 1
Name: count, Length: 457, dtype: int64
linnean["recipient_agr"].value_counts()
recipient_agr
Smith_Sir_James_Edward 2948
Macleay_Alexander 102
Smith_Pleasance 72
Roscoe_William 53
Unknown_nan 51
...
Sutton_Charles 1
Brandreth_Mrs 1
Bright_Richard 1
Walker_George 1
Reeve_Robert 1
Name: count, Length: 65, dtype: int64
V obou případech vidíme na prvním místě Sira Jamese Edwarda Smithe. Což, víme-li něco o Linneovské společnosti nebo podíváme-li se na wikipedii, není příliš překvapivé: jedná se o samotného zakladatele a dlouholetého předsedu této společnosti (viz wikipedia)).
V druhé tabulce vidíme na třetím místě také jeho manželku, Pleasance Smithovou, která byla taktéž významnou osobností dobového dění (taktéž viz wikipedie).
Tvorba síťových dat¶
Pro potřeby následujících si naše data výrazně přeskupíme a přetvoříme do podoby seznamu vážených vazeb.
linnean_edges = linnean.groupby(["sender_agr", "recipient_agr"]).size().reset_index()
linnean_edges.columns = ["sender_agr", "recipient_agr", "letters_n"]
linnean_edges.head()
| sender_agr | recipient_agr | letters_n | |
|---|---|---|---|
| 0 | Abbot_Charles | Smith_Sir_James_Edward | 18 |
| 1 | Acharius_Erik | Smith_Sir_James_Edward | 8 |
| 2 | Acrel_Johan_Gustaf | Smith_Sir_James_Edward | 7 |
| 3 | Afzelius_Adam | Smith_Sir_James_Edward | 14 |
| 4 | Aiton_William_Townsend | Smith_Sir_James_Edward | 1 |
Jednotkou pozorování (čili řádkou tabulky) nyní již není každý jednotlivý dopis, ale pár odesilatele a příjemce s informací, kolik odesilatel příjemci zaslal dopisů (viz sloupec "letters_n"). Můžeme podívat na tabulku hran setříděnou od těch s největší váhou (tj. s nejvyšším počtem dopisů poslaných daným směrem).
linnean_edges.sort_values("letters_n", ascending=False)
| sender_agr | recipient_agr | letters_n | |
|---|---|---|---|
| 189 | Goodenough_Samuel | Smith_Sir_James_Edward | 222 |
| 413 | Smith_Sir_James_Edward | Macleay_Alexander | 102 |
| 525 | Woodward_Thomas_Jenkinson | Smith_Sir_James_Edward | 101 |
| 348 | Roscoe_William | Smith_Sir_James_Edward | 94 |
| 241 | Johnes_Thomas | Smith_Sir_James_Edward | 83 |
| ... | ... | ... | ... |
| 352 | Rous_Charlotte_Maria | Smith_Sir_James_Edward | 1 |
| 353 | Rowden_Frances_Arabella | Smith_Sir_James_Edward | 1 |
| 158 | Erskine_David_Steuart | Smith_Sir_James_Edward | 1 |
| 157 | Engelhart_John_Henry | Smith_Sir_James_Edward | 1 |
| 533 | Zimmermann_Eberhard_August_Wilhelm | Smith_Sir_James_Edward | 1 |
534 rows × 3 columns
G = nx.from_pandas_edgelist(linnean_edges, 'sender_agr', 'recipient_agr', 'letters_n', create_using=nx.DiGraph())
type(G)
networkx.classes.digraph.DiGraph
Základní vlastnosti, které nás o našem grafu zajímají jsou, kolik má uzlů a kolik má hran?
G.number_of_nodes()
476
G.number_of_edges()
534
Další užitečnou informací je, kolik mají uzle v průměru vazeb (tzv. avarege degree).
sum(dict(G.degree).values()) / G.number_of_nodes()
2.2436974789915967
Stejně tak zajímavé bude se podívat, který uzle mají nejvyšší in-degree (tj. vazeb do něj vstupujících) a out-degree (tj. vazeb z něj vystupujících). Podívejme se na deset uzlů s nejvyšší hodnotou in-degree:
sorted(dict(G.in_degree()).items(), key=lambda item: item[1], reverse=True)[:10]
[('Smith_Sir_James_Edward', 445),
('Unknown_nan', 14),
('Smith_Pleasance', 6),
('Cullum_Sir_Thomas_Gery', 4),
('Lambert_Aylmer_Bourke', 2),
('Wallich_Nathaniel', 2),
('Goodenough_Samuel', 2),
('The_Linnean_Society_nan', 2),
('Banks_Sir_Joseph', 1),
('Barrington_Shute', 1)]
Vidíme, že zcela ústřední pozici zde zaujímá Sir James Edward Smith, zakladatel a dlouholetý předseda společnosti. Hned na druhém místě se v jednom uzlu potkávají dopisy, jejichž adresát je neznámý. Nebude od věci tento uzel ze sítě zcela odstranit.
G.remove_node("Unknown_nan")
Utvořený síťový graf si můžeme bezprostřdně vizualizovat pomocí funkce nx.draw():
nx.draw(G)
Bohužel vidíme, že výsledek vypadá spíše nevábně. Podle všeho se zde příliš mnoho uzlů poblíž středu. Vidíme, že vazby mají podobu šipek. Je tomu tak proto, že se jedná o tzv. směrový graf.
Abychom dosáhli lepších výsledků, přidáme do vizualizační funkce několik dodatečných parametrů
nx.draw(G, node_size=20, node_color="darkgreen", pos=nx.kamada_kawai_layout(G))
Uzly v grafu se jmenují stejně jako korespondenti. Pomocí syntaxe níže se tak můžeme podívat na vlastnosti jednotlivých vazeb.
G["Smith_Sir_James_Edward"]["Macleay_Alexander"]
{'letters_n': 102}
G["Macleay_Alexander"]["Smith_Sir_James_Edward"]
{'letters_n': 74}
Zde se dozvídáme, že zatímco Sir James Edward Smith poslal Alexanderu Macleayovi 102, v opačném směru jich šlo 74.
Pro některé typy analýz je praktičtější i smysluplnější pracovat s nesměrovým grafem. Vazba tak nezohledňuje směr příslušné korespondence a váha může odpovídat součtu vyměněných dopisů v obou směrech. Transformovat naši síť do této podoby vyžaduje několik řádek kódy, jimiž se zde nemusíme příliš zaobírat, důležitější je výsledek.
to_remove = []
edges_met = []
for node1, node2 in G.edges():
if (G.has_edge(node2, node1)) & ((node2, node1) not in edges_met):
G[node1][node2]["letters_n"] = G[node1][node2]["letters_n"] + G[node2][node1]["letters_n"]
to_remove.append((node2, node1))
edges_met.append((node1, node2))
len(edges_met)
519
len(to_remove)
35
for u,v in to_remove:
G.remove_edge(u,v)
G = G.to_undirected().copy()
len(G.edges())
484
G["Smith_Sir_James_Edward"]["Macleay_Alexander"]
{'letters_n': 176}
G["Macleay_Alexander"]["Smith_Sir_James_Edward"]
{'letters_n': 176}
weighted_degrees = {}
for node in G.nodes():
weighted_degrees[node] = G.degree(node, weight='letters_n')
list(weighted_degrees.items())[:10]
[('Abbot_Charles', 18),
('Smith_Sir_James_Edward', 3418),
('Acharius_Erik', 8),
('Acrel_Johan_Gustaf', 7),
('Afzelius_Adam', 14),
('Aiton_William_Townsend', 1),
('Allioni_Carlo', 7),
('Anderson_Alexander', 2),
('Anderson_James', 2),
('Anguish_Mrs_S', 1)]
# tento degree učiníme atributem našich uzlů
nx.set_node_attributes(G, weighted_degrees, 'weighted_degree')
Nyní si vyjmeme pouze uzly, které mají stupeň alespoň roven 2, tj. uzly osob, kteří v našem datasetu vedly korespondenci s více než jednou osobou.
node_list = [node for node in G.nodes if G.degree(node) >= 2]
len(node_list)
28
Ukazuje se, že takových uzlů je v našem datasetu relativně málo. Vypišme si jejich jména.
node_list
['Smith_Sir_James_Edward', 'Barrington_Jane', 'Lambert_Aylmer_Bourke', 'Sutton_Charles', 'Bicheno_James_Ebenezer', 'Forster_Edward', 'Boyd_George', 'Roxburgh_William', 'Brodie_James', 'Coke_Thomas_William', 'Wallich_Nathaniel', 'Crowe_James', 'Cullum_Sir_Thomas_Gery', 'Smith_Pleasance', 'Davy_Martin', 'Don_George', 'Goodenough_Samuel', 'Drake_William_Fitt', 'Gemmellaro_Carlo', 'The_Linnean_Society_nan', 'Gurney_Anna', 'Harriman_John', 'Johnes_Thomas', 'Latham_John', 'Martyn_Thomas', 'Smith_James', 'Swartz_Olof_Peter', 'Webb_William']
Nyní tento seznam jmen využijeme k vymezení výseku z našeho grafu (nazveme si jej Gsub), který bude zahrnovat pouze tyto uzly.
Gsub = G.subgraph(node_list)
fig, ax = plt.subplots(1,1, figsize=(9, 6), dpi=300, tight_layout=True)
# pro potřeby vizualizace si ještě definujeme šířku čar jednotlivých vazeb,vycházející z objemu vyměněných dopisů.
edge_widths = [np.sqrt(d['letters_n']) / 2 for (u, v, d) in Gsub.edges(data=True)]
nx.draw(Gsub, with_labels=True, pos=nx.kamada_kawai_layout(Gsub), node_size=100, nodelist=node_list, width=edge_widths, ax=ax)
ax.set_xlim(-1.3, 1.3)
(-1.3, 1.3)
Z takovéto vizualizace již lze vypozorovat leccos.
Cvičení 2: Britská vědecká korespondence dlouhého 19. století jako celek¶
Extrace a předzpracování dat¶
Nyní se vrátíme na začátek. Projekt Ɛpsilon totiž hostí vícero kolekcí dopisů z podobného období a je na místě očekávat, že se osoby v těchto kolekcích budou alespoň částečně překrývat.
Vypišme si tedy nejprve jména csv souborů s metadaty k těmto kolekcím.
resp_json = requests.get("https://github.com/cambridge-collection/epsilon-data/tree/main/csv").json()
filenames = [item["name"] for item in resp_json["payload"]["tree"]["items"]]
filenames
['ampere.csv', 'darwin-correspondence.csv', 'darwin-family-letters.csv', 'faraday.csv', 'henslow.csv', 'herschel.csv', 'kemp.csv', 'linnean-society.csv', 'royal-society.csv', 'somerville.csv', 'tyndall.csv']
Nyní pomocí cyklu FOR načteme data ze všech těchto souborů a nakonec je spojíme do jednoho objektu type pd.DataFrame.
dfs = [] # připrav prázdný seznam, který budeme následně postupně plnit daty z jednotlivých kolekcí
for filename in filenames: # pro každý z našeho seznamu souborů:
try: # zkus: jej načíst jako dataframe
collection_df = pd.read_csv("https://raw.githubusercontent.com/cambridge-collection/epsilon-data/main/csv/" + filename)
collection_df["source"] = filename # přidej tomuto dataframu nový sloupec "source", kde bude uvedeno jméno souboru, ze kterého pochází
dfs.append(collection_df) # přidej do seznamu aktuální dataframe
except: # pokud to nejde:
print("failed: ", filename) # vypiš jméno souboru, u kterého to nejde
epsilon = pd.concat(dfs) # spoj do jednoho všechny dataframy uvnitř seznamu dfs
failed: darwin-family-letters.csv
epsilon.head(5)
| id | sender_surname | sender_forename | recipient_surname | recipient_forename | sorting_date | date | sender_address | recipient_address | source | languages | extent | filename | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | L1 | Ampère | Jeanne-Antoinette (mère d'Ampère) | Ampère | André-Marie | 1775-01-01 | s.d. | NaN | NaN | ampere.csv | fra | NaN | L1.xml |
| 1 | L2 | Maine de Biran | Pierre | Ampère | André-Marie | 1807-03-15 | 15 mars 1807 | NaN | NaN | ampere.csv | fra | NaN | L2.xml |
| 2 | L3 | Ampère | André-Marie | Ampère | Jean-Jacques (fils d'Ampère) | 1775-01-01 | s.d. | NaN | NaN | ampere.csv | fra | NaN | L3.xml |
| 3 | L4 | Ampère | André-Marie | Duhamel | Jean-Marie | 1775-01-01 | s.d. | NaN | NaN | ampere.csv | fra | NaN | L4.xml |
| 4 | L5 | Ampère | André-Marie | Duhamel | Jean-Marie | 1775-01-01 | s.d. | NaN | NaN | ampere.csv | fra | NaN | L5.xml |
# jak dlouhý je náš dataset?
len(epsilon)
47459
# stejně jako výše agregujme jména autorů a příjemců dopisů do podoby bez mezer a závorek
epsilon["sender_agr"] = epsilon.apply( lambda row: str(row["sender_surname"]).replace(" ", "_").partition(" (")[0] + "_" + str(row["sender_forename"]).replace(" ", "_").partition(" (")[0], axis=1)
epsilon["sender_agr"] = epsilon["sender_agr"].apply(lambda x: regex.sub("[^\p{L}_-]", "", x))
epsilon["recipient_agr"] = epsilon.apply( lambda row: str(row["recipient_surname"]).replace(" ", "_").partition(" (")[0] + "_" + str(row["recipient_forename"]).replace(" ", "_").partition(" (")[0], axis=1)
epsilon["recipient_agr"] = epsilon["recipient_agr"].apply(lambda x: regex.sub("[^\p{L}_-]", "", x))
Vypišme si nejplodnější autory a nejpopulárnější příjemce:
epsilon["sender_agr"].value_counts()
sender_agr
Darwin_C_R 8151
Herschel_Sir_John 5353
Faraday_Michael 2985
Tyndall_John 1146
Airy_George_Biddell 751
...
Bunbury_E_H 1
Jacob_Edward 1
Smirke_E 1
Copley_J_S 1
Bohn_Johann_C 1
Name: count, Length: 5763, dtype: int64
epsilon["recipient_agr"].value_counts()
recipient_agr
Herschel_Sir_John 9305
Darwin_C_R 6713
Smith_Sir_James_Edward 2948
Faraday_Michael 2102
Tyndall_John 1291
...
Humboldt_Friedrich_Wilhelm_Alexander_von 1
Plummer_Isabella_Erskine 1
Magendie_François 1
Ayres_Philip_Burnard 1
Clausius_Adelheid 1
Name: count, Length: 3945, dtype: int64
Tentokrát si data vazeb do nesměrové podoby převedeme ještě před vytvořením grafu.
epsilon_temp = epsilon.apply(lambda row: pd.Series(sorted([str(row["sender_agr"]), str(row["recipient_agr"])])), axis=1)
epsilon_temp.columns = ["node1", "node2"]
epsilon_edges = epsilon_temp.groupby(["node1", "node2"]).size().reset_index()
epsilon_edges.columns = ["node1", "node2", "weight"]
epsilon_edges = epsilon_edges[epsilon_edges["node1"] != epsilon_edges["node2"]]
epsilon_edges.head(5)
| node1 | node2 | weight | |
|---|---|---|---|
| 0 | AB_Hewetson_nan | Tristram_Henry_Baker | 1 |
| 1 | AB_nan | Faraday_Michael | 2 |
| 2 | AT_TO_LOOK | Unknown_nan | 1 |
| 3 | AW_Williamson_Foreign_Secretary_Royal_Society | Williamson_Alexander_William | 1 |
| 4 | A_B | Royal_Society_nan | 1 |
Data v této podobě můžeme již neprodleně použít k tvorbě sítě váženého nesměrového grafu.
G = nx.from_pandas_edgelist(epsilon_edges, 'node1', 'node2', 'weight')
Opět se nejprve podíváme, z kolika uzlů a kolika hran naše síť sestává:
G.number_of_nodes()
7646
G.number_of_edges()
9088
Z těchto dat lze také snadno vypočítat tzv. average degree:
(2 * G.number_of_edges()) / G.number_of_nodes()
2.377190687941407
U grafu s takto velkým počtem uzlů se nezřídka stane, že se ukáže, že je ve skutečnosti tvořen několika oddělenými komponenty, čili že síť není zcela propojená.
len(list(nx.connected_components(G)))
166
Ano, to je i náš případ zde, když máme co dočinění s grafem, který sestává z více než 160 komponentů.
Podívejme se, z kolika uzlů sestává deset největších komponentů:
components_sorted = sorted(list(nx.connected_components(G)), key=len, reverse=True)
[len(comp) for comp in components_sorted][:10]
[7295, 5, 4, 4, 3, 3, 3, 3, 3, 3]
Vidíme, že většina uzlů je součástí největšího komponentu, druhý největší komponent sestává již pouze z 5 uzlů. S klidným svědomím se nyní zaměříme pouze na největší komponent naší sítě.
len(components_sorted[0])
7295
# Omezíme se na největší komponent.
G = G.subgraph(list(components_sorted[0]))
G.number_of_nodes() #zkontrolujeme, že se filtrace uzlů povedla
7295
Pro potřeby několika dalších vizualizací nyní všem uzlům v rámci této sítě přiřadíme pozici v prostoru na základě jejich strukturelního postavení. Přiřazení těchto pozic v případě sítě, která sestává z tisíců uzlů, může být výpočetně poměrně náročné a zabrat nějaký čas. Abychom se níže vyhnuli zbytečnému čekání, vypočteme si tyto pozice uzlů již zde a dále je budeme používat v několika vizualizacích po sobě.
%%time
pos = nx.spring_layout(G)
CPU times: user 51.8 s, sys: 122 ms, total: 51.9 s Wall time: 52.6 s
fig, ax = plt.subplots(figsize=(9,6), dpi=300)
nx.draw(G, node_size=10, node_color="darkgreen", pos=pos, ax=ax)
Tato síť již možná má některé zajímavé topografické vlastnosti, které si zaslouží bližší analytické ohledání.
Metriky centrality¶
Jedna skupina populárních a užitečných algoritmů jsou tzv. metriky centrality uzlů či vazeb. Uveďme si dvě takové metriky s jejich anglickými názvy a krátkým vysvětlením nejznámnější s jejich anglickými názvy:
- degree centrality: je definován počtem vazeb, které daný uzel má
- closeness centrality: součet vzdáleností nejkratších cest potřebných k dosažení všech ostatních uzlů uvnitř sítě.
- betweenness centrality (mezilehlost): Jak často se ten který uzel nachází na trase spojující nejkratší cestou jakékoli další uzly uvnitř sítě.
- PageRank centrality: je určen mnohonásobně opakovanými náhodnými procházkami po síti. Velikost PageRank je určena množstvím návštěv daného uzlu při těchto procházkách. Tento algoritmus byl původně vyvinut vývojáři od společnosti pro určení důležitých webových stránek.
S degree centrality jsme již vlastně pracovali, když jsme se u předchozí sítě omezili pouze na uzly s degree alespoň 2. Tato metrika je také nejsnáze srozumitelná a bude zajímavé si zde představit její výsledky pro potřeby srovnání s výsledky ostatních metrik. Jelikož zde však pracujeme s relativně rozsáhlou sítí a náš společný čas je omezený, vyzkoušíme si nyní pouze algrotimus pro PageRank, který je výpočetně nejméně náročný.
degree_centrality = nx.degree_centrality(G)
degree_top_nodes = sorted(degree_centrality.items(), key=lambda x:x[1], reverse=True)
degree_top_nodes[:10]
[('Darwin_C_R', 0.27337537702221004),
('Herschel_Sir_John', 0.24362489717576088),
('Faraday_Michael', 0.1616397038661914),
('Smith_Sir_James_Edward', 0.06292843432958596),
('Tyndall_John', 0.0527831094049904),
('Henslow_J_S', 0.04154099259665478),
('Royal_Society_nan', 0.029064984919111598),
('nan_nan', 0.027282698108034),
('Ampère_André-Marie', 0.02604880723882643),
('Banks_Joseph', 0.01946805593638607)]
pagerank_centrality = nx.pagerank(G, max_iter=10000)
pagerank_top_nodes = sorted(pagerank_centrality.items(), key=lambda x:x[1], reverse=True)
pagerank_top_nodes[:10]
[('Darwin_C_R', 0.12531743230350081),
('Herschel_Sir_John', 0.11578752463912399),
('Faraday_Michael', 0.057520944520063226),
('Smith_Sir_James_Edward', 0.028529193763289443),
('Tyndall_John', 0.022548106020346178),
('Henslow_J_S', 0.01330130754811916),
('Ampère_André-Marie', 0.011978899884381007),
('Hooker_J_D', 0.010425398525256518),
('Royal_Society_nan', 0.009683475973305872),
('nan_nan', 0.009509369237027814)]
%%time
betweenness_centrality = nx.betweenness_centrality(G)
betweenness_top_nodes = sorted(betweenness_centrality.items(), key=lambda x:x[1], reverse=True)
betweenness_top_nodes[:10]
CPU times: user 3min 1s, sys: 935 ms, total: 3min 2s Wall time: 3min 8s
[('Darwin_C_R', 0.4609313877075591),
('Herschel_Sir_John', 0.3988460586117793),
('Faraday_Michael', 0.30407842842289146),
('Smith_Sir_James_Edward', 0.1125311165691395),
('nan_nan', 0.09766682496924398),
('Tyndall_John', 0.09335990395332099),
('Royal_Society_nan', 0.07192907238232374),
('Henslow_J_S', 0.0656112688904613),
('Ampère_André-Marie', 0.04860372542234724),
('Banks_Joseph', 0.048231610499014956)]
degree_pagerank_comparison = []
for deg, page, betw in zip(degree_top_nodes, pagerank_top_nodes, betweenness_top_nodes):
degree_pagerank_comparison.append([deg[0], page[0], betw[0]])
centr_comparison_df = pd.DataFrame(degree_pagerank_comparison)
centr_comparison_df.columns = ["degree_node", "pagerank_node", "betw_node"]
print(centr_comparison_df.head(20).round(2))
degree_node pagerank_node betw_node 0 Darwin_C_R Darwin_C_R Darwin_C_R 1 Herschel_Sir_John Herschel_Sir_John Herschel_Sir_John 2 Faraday_Michael Faraday_Michael Faraday_Michael 3 Smith_Sir_James_Edward Smith_Sir_James_Edward Smith_Sir_James_Edward 4 Tyndall_John Tyndall_John nan_nan 5 Henslow_J_S Henslow_J_S Tyndall_John 6 Royal_Society_nan Ampère_André-Marie Royal_Society_nan 7 nan_nan Hooker_J_D Henslow_J_S 8 Ampère_André-Marie Royal_Society_nan Ampère_André-Marie 9 Banks_Joseph nan_nan Banks_Joseph 10 Somerville_Mary Airy_George_Biddell Watson_William 11 Folkes_Martin Banks_Joseph Somerville_Mary 12 Mortimer_Cromwell Sabine_Edward Sabine_Edward 13 Birch_Thomas Somerville_Mary Folkes_Martin 14 Wedgwood_Emma Babbage_Charles Lyell_Charles 15 Herschel_Margaret_Brodie Mortimer_Cromwell Mortimer_Cromwell 16 Pringle_John Herschel_Margaret_Brodie Galton_Francis 17 Maskelyne_Nevil Hirst_Thomas_Archer Phillips_John 18 Sabine_Edward Folkes_Martin Lubbock_John 19 Parker_George De_Morgan_Augustus Birch_Thomas
V čem je toto srovnání potenciálně zajímavé? Podíváme-li se na pravou stranu tabulky, tj. uzly s největší betweenness centralitou, vidíme, že zejména ve druhé desítce se nachází nemálo uzlů, se kterými se na levé straně (u degree centrality) v první dvacítce vůbec nesetkáváme: Jinými slovy, jedná se o uzly, jejichž centralita v rámci sítě není živena výlučně množstvím vazeb, které uvnitř sítě mají, ale spíše specifickým strukturálním postavením. Podívejme se tedy na stejná data ještě jiným způsobem a totiž vypišme si, na kolikáté pozici se dvacítka uzlů s nejvyšší beteweenness centrality nachází z hlediska degree centrality.
for node in centr_comparison_df["betw_node"][:20]:
print(node, " degree:", G.degree(node), "degree rank:", [el[0] + 1 for el in enumerate(degree_top_nodes) if el[1][0] == node][0], )
Darwin_C_R degree: 1994 degree rank: 1 Herschel_Sir_John degree: 1777 degree rank: 2 Faraday_Michael degree: 1179 degree rank: 3 Smith_Sir_James_Edward degree: 459 degree rank: 4 nan_nan degree: 199 degree rank: 8 Tyndall_John degree: 385 degree rank: 5 Royal_Society_nan degree: 212 degree rank: 7 Henslow_J_S degree: 303 degree rank: 6 Ampère_André-Marie degree: 190 degree rank: 9 Banks_Joseph degree: 142 degree rank: 10 Watson_William degree: 39 degree rank: 21 Somerville_Mary degree: 119 degree rank: 11 Sabine_Edward degree: 41 degree rank: 19 Folkes_Martin degree: 72 degree rank: 12 Lyell_Charles degree: 19 degree rank: 39 Mortimer_Cromwell degree: 68 degree rank: 13 Galton_Francis degree: 12 degree rank: 66 Phillips_John degree: 8 degree rank: 109 Lubbock_John degree: 16 degree rank: 48 Birch_Thomas degree: 66 degree rank: 14
Podívejme se nyní čtyři osobnosti:
- Charles Lyell
- Francis Galton
- John Phillips
- John Lubbock
Jejich degree rank je ve srovnání s jejich betweenness relativně vysoký. Zdá se, že tedy uzly mají v rámci grafu strukturálně zajímovou pozici.
Vytvořme tedy novou vizualizaci, v rámci které zaostříme pozornost právě na 20 uzlů s největší betweenness. Tyto uzly vyobrazíme odlišnou barvou a stejnou barvou vyobrazíme i jejich jména.
special_nodes = centr_comparison_df["betw_node"][:20] #["Lyell_Charles", "Galton_Francis", "Phillips_John", "Lubbock_John"]
special_pos = dict([(node, pos[node]) for node in special_nodes])
labels = {node: node for node in special_nodes}
fig, ax = plt.subplots(figsize=(24,18), dpi=300)
nx.draw(G, node_size=10, node_color="black", edge_color="grey",pos=pos, ax=ax, alpha=0.5)
nx.draw_networkx_nodes(G, nodelist=special_nodes, node_size=50, node_color="darkorange", pos=special_pos, ax=ax)
nx.draw_networkx_labels(G, font_color="darkorange", pos=special_pos, labels=labels,ax=ax)
{'Darwin_C_R': Text(-0.24240782856941223, -0.1835523545742035, 'Darwin_C_R'),
'Herschel_Sir_John': Text(-0.05920654907822609, 0.03125627711415291, 'Herschel_Sir_John'),
'Faraday_Michael': Text(0.07666870206594467, -0.009823252446949482, 'Faraday_Michael'),
'Smith_Sir_James_Edward': Text(0.2576848864555359, -0.1726907342672348, 'Smith_Sir_James_Edward'),
'nan_nan': Text(0.23327383399009705, 0.29523658752441406, 'nan_nan'),
'Tyndall_John': Text(0.007323220372200012, -0.1337890326976776, 'Tyndall_John'),
'Royal_Society_nan': Text(0.2958509624004364, 0.3393012285232544, 'Royal_Society_nan'),
'Henslow_J_S': Text(-0.20399868488311768, -0.05321016162633896, 'Henslow_J_S'),
'Ampère_André-Marie': Text(0.08214311301708221, 0.233653724193573, 'Ampère_André-Marie'),
'Banks_Joseph': Text(0.34255313873291016, 0.20324811339378357, 'Banks_Joseph'),
'Watson_William': Text(0.3264940083026886, 0.26460760831832886, 'Watson_William'),
'Somerville_Mary': Text(0.004037114791572094, -0.06527800112962723, 'Somerville_Mary'),
'Sabine_Edward': Text(-0.021545175462961197, -0.006618051324039698, 'Sabine_Edward'),
'Folkes_Martin': Text(0.3287908732891083, 0.48453035950660706, 'Folkes_Martin'),
'Lyell_Charles': Text(-0.14943693578243256, -0.14990419149398804, 'Lyell_Charles'),
'Mortimer_Cromwell': Text(0.44783398509025574, 0.5267356038093567, 'Mortimer_Cromwell'),
'Galton_Francis': Text(-0.18355107307434082, -0.10792119801044464, 'Galton_Francis'),
'Phillips_John': Text(-0.10157318413257599, -0.041374366730451584, 'Phillips_John'),
'Lubbock_John': Text(-0.18244527280330658, -0.14187228679656982, 'Lubbock_John'),
'Birch_Thomas': Text(0.43442702293395996, 0.44949376583099365, 'Birch_Thomas')}
Aby byl text čitelný a graf přehledný, vizualizace výše je výrazně větší než ty předchozí. Uložíme si ji do samostatného souboru ve formátu png.
try:
fig.savefig("../figures/epsilon_betw.png") # pokud pracujeme s repozitoří jako celkem, včetně podlsožky "figures"
except:
fig.savefig("epsilon_betw.png") # pokud pracujeme s notebookem samostatně, např. přes Google Colab
Detekce komunit¶
Další důležitou rodinou algoritmů jsou algoritmy pro detekování komunit, neboli shluků uzlů, které jsou mezi sebou provázány více, než z uzly z jejich okolí. Zde použijeme takzvanou Lovaňskou metodu (podle působiště výzkumníků, kteří ji vyvinuli [viz wikipedia]). Tento algoritmus se snaží nalézt takové rozdělení uzlů do komunit, které maximalizuje poměr vazeb mezi uzly uvnitř těchto komunit oproti jejich vazbám směrem ven z těchto komunit.
from networkx.algorithms import community
communities = nx.community.louvain_communities(G, seed=1)
len(communities)
16
Algoritmus identifikoval 16 komunit. Podívejme se nejprve, kolik jednotlivé komunity čítají uzlů:
[len(com) for com in communities]
[1104, 1081, 461, 184, 11, 259, 1989, 2, 3, 102, 332, 1692, 3, 2, 68, 2]
cmap = plt.get_cmap('viridis')
colors = [cmap(i) for i in np.linspace(0, 1, len(communities))]
fig, ax = plt.subplots(figsize=(24,18), dpi=300)
nx.draw_networkx_edges(G, edge_color="grey",pos=pos, alpha=0.5, ax=ax)
for community, color in zip(communities, colors):
special_pos = dict([(node, pos[node]) for node in list(community)])
#nx.draw(G, node_size=10, node_color="black", edge_color="grey",pos=pos, ax=ax, alpha=0.5)
nx.draw_networkx_nodes(G, nodelist=list(community), node_size=10, node_color=[color], pos=special_pos, ax=ax)
ax.axis('off')
(-0.7456697627902031, 1.1317883536219597, -0.754230284690857, 1.1666915655136108)
Vidíme, že tento algoritmus tedy dokáže velice pěkně zachytit strukturální vlastnosti dané sítě. To je v případě rozsáhlých grafů velice užitečné.
correspsearch = pd.read_csv("https://correspsearch.net/api/v2.0/csv.xql?", sep=";")
correspsearch.head(10)
| sender | senderID | senderPlace | senderPlaceID | senderDate | addressee | addresseeID | addresseePlace | addresseePlaceID | addresseeDate | edition | key | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Kf. Friedrich | http://d-nb.info/gnd/11853579X | NaN | NaN | NaN | Universität Wittenberg | http://d-nb.info/gnd/4032660-3 | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 464 |
| 1 | Alexius Crosner | http://d-nb.info/gnd/128693517 | Leipzig | http://sws.geonames.org/2879139 | 1510 | Julius Pflug | http://d-nb.info/gnd/118714082 | keine Angabe | NaN | NaN | Julius Pflug. Correspondance, recueillie et éd... | 1 |
| 2 | Melanchthon | http://d-nb.info/gnd/118580485 | Tübingen | http://sws.geonames.org/2820860 | NaN | Geraeander, Paul | http://d-nb.info/gnd/1140261282 | Tübingen | http://sws.geonames.org/2820860 | NaN | Melanchthon Briefwechsel: Regesten online. Im ... | 6a |
| 3 | Kf. Friedrich Hz. Johann | http://d-nb.info/gnd/11853579X http://d-nb.inf... | Torgau | http://sws.geonames.org/2821807 | 1513-01-06 | Bf. Johann III. von Naumburg | http://d-nb.info/gnd/139152156 | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 5 |
| 4 | Räte Kf. Friedrichs | NaN | Torgau | http://sws.geonames.org/2821807 | 1513-01-14 | Bf. [Hieronymus] von Brandenburg | http://d-nb.info/gnd/137650752 | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 6 |
| 5 | Bf. Hieronymus von Brandenburg | http://d-nb.info/gnd/137650752 | Ziesar | http://sws.geonames.org/2804279 | 1513-01-24 | Räte Kf. Friedrichs | NaN | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 7 |
| 6 | Wolfgang Zesche Konvent des Augustinereremiten... | http://d-nb.info/gnd/7754053-0 | [Herzberg] | http://sws.geonames.org/2905504 | 1513-01-30 | Kf. Friedrich | http://d-nb.info/gnd/11853579X | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 8 |
| 7 | Dekan [Eucharius Spiecker] Kapitel des Mariens... | [Eisenach] | http://sws.geonames.org/2931574 | 1513-02-01 | Kf. Friedrich Hz. Johann | http://d-nb.info/gnd/11853579X http://d-nb.inf... | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 9 | |
| 8 | Kf. Friedrich Hz. Johann | http://d-nb.info/gnd/11853579X http://d-nb.inf... | Weimar | http://sws.geonames.org/2812482 | 1513-03-06 | Bf. Johann III. von Naumburg | http://d-nb.info/gnd/139152156 | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 13 |
| 9 | Kf. Friedrich | http://d-nb.info/gnd/11853579X | Eilenburg | http://sws.geonames.org/2931871 | 1513-03-16 | Hz. Georg von Sachsen | http://d-nb.info/gnd/118716921 | NaN | NaN | NaN | Briefe und Akten zur Kirchenpolitik Friedrichs... | 14 |
%%time
for n in range(2,30):
page_df = pd.read_csv("https://correspsearch.net/api/v2.0/csv.xql?x=" + str(n), sep=";")
correspsearch = pd.concat([correspsearch, page_df])
if n in range(0,3000,100):
print(n)
if len(page_df) < 100:
break
CPU times: user 356 ms, sys: 58.7 ms, total: 414 ms Wall time: 15.5 s
len(correspsearch)
3036
correspsearch = correspsearch[correspsearch["sender"].notnull() & correspsearch["addressee"].notnull()]
len(correspsearch)
2836
